/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 */
var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  const n = coins.length;
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    dp[i] = Number.MAX_VALUE;
    for (let j = 0; j < n; j++) {
      if (i >= coins[j]) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
};

console.log(coinChange([474, 83, 404, 3], 264));
